package org.example;

import java.util.ArrayList;
import java.util.HashMap;

// [前缀和]
// 前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。
// 局限性一：使用前缀和技巧的前提是原数组nums不会发生变化；
// 局限性二：前缀和技巧只适用于存在逆运算的场景
public class PrefixSum {
    // 一维数组中的前缀和
    // 303. 区域和检索 - 数组不可变
    // 给定一个整数数组  nums，处理以下类型的多个查询:
    // 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
    // 实现 NumArray 类：
    // NumArray(int[] nums) 使用数组 nums 初始化对象
    // int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )
    static class NumArray {
        // 前缀和数组
        private int[] preSum;

        // 输入一个数组，构造前缀和
        public NumArray(int[] nums) {
            // preSum[0] = 0; 便于计算累加和
            preSum = new int[nums.length + 1];
            // 计算nums的累加和
            for (int i = 1; i < preSum.length; i++) {
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
        }

        // 查询闭区间[left, right]的累加和，注意这里是right是闭区间
        public int sumRange(int left, int right) {
            return preSum[right + 1] - preSum[left];
        }
    }

    // 这种方式也可
    static class PrefixSumTemplate {
        // 计算一维数组的前缀和数组
        public static int[] prefixSum1D(int[] nums) {
            int n = nums.length;
            int[] prefixSum = new int[n];
            prefixSum[0] = 0;
            for (int i = 1; i < n; i++) {
                prefixSum[i] = prefixSum[i - 1] + nums[i];
            }
            return prefixSum;
        }

        public static int rangeSum(int[] preSum, int left, int right) {
            // 这里的left == 0 需要单独处理
            if (left == 0) {
                return preSum[right];
            }
            return preSum[right] - preSum[left - 1];
        }
    }

    // 二维矩阵中的前缀和
    // 二维矩阵前缀和 preSum[i][j] 表示从矩阵左上角 (0, 0) 到 (i - 1, j - 1) 所围成的子矩阵中所有元素的和。
    // 求范围和的原理
    // 假设我们要求矩阵中从 (x1, y1) 到 (x2, y2) 这个子矩阵的元素和。
    // 我们可以把 preSum[x2 + 1][y2 + 1] 看作是从矩阵左上角 (0, 0) 到 (x2, y2) 这个大子矩阵的元素和。但这个大子矩阵包含了我们不需要的部分，需要减去多余的区域。
    // preSum[x1][y2 + 1]：它表示从矩阵左上角 (0, 0) 到 (x1 - 1, y2) 这个子矩阵的元素和。从 preSum[x2 + 1][y2 + 1] 中减去它，就相当于去掉了大子矩阵中 x 坐标小于 x1 的那部分区域。
    // preSum[x2 + 1][y1]：它表示从矩阵左上角 (0, 0) 到 (x2, y1 - 1) 这个子矩阵的元素和。从 preSum[x2 + 1][y2 + 1] 中减去它，就相当于去掉了大子矩阵中 y 坐标小于 y1 的那部分区域。
    // 然而，在减去 preSum[x1][y2 + 1] 和 preSum[x2 + 1][y1] 时，(0, 0) 到 (x1 - 1, y1 - 1) 这个子矩阵的和被减了两次，所以需要再加上 preSum[x1][y1] 把多减去的部分补回来。
    static class NumMatrix {
        // preSum[i][j] 记录矩阵[0, 0, i-1, j-1]的元素和
        private int[][] preSum;

        public NumMatrix(int[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            if (m == 0 || n == 0) {
                return;
            }
            // 构造前缀和矩阵
            preSum = new int[m + 1][n + 1];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    // 计算每个矩阵[0, 0, i, j]的元素和
                    preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
                }
            }
        }

        // 计算子矩阵[x1, y1, x2, y2]的元素和
        public int sumRegion(int x1, int y1, int x2, int y2) {
            // 目标矩阵之和由四个相邻矩阵运算获得
            // 要求矩阵中从 (x1, y1) 到 (x2, y2) 这个子矩阵的元素和
            return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
        }
    }

    // 一：前缀和
    // 1314. 矩阵区域和
    // 给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
    // i - k <= r <= i + k,
    // j - k <= c <= j + k 且
    // (r, c) 在矩阵内。
    // 示例 1：
    // 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
    // 输出：[[12,21,16],[27,45,33],[24,39,28]]
    static class MatrixBlockSum {
        public int[][] matrixBlockSum(int[][] mat, int k) {
            int m = mat.length;
            int n = mat[0].length;
            NumMatrix numMatrix = new NumMatrix(mat);
            int[][] res = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 左上角的坐标
                    int x1 = Math.max(i - k, 0);
                    int y1 = Math.max(j - k, 0);
                    int x2 = Math.min(i + k, m - 1);
                    int y2 = Math.min(j + k, n - 1);
                    res[i][j] = numMatrix.sumRegion(x1, y1, x2, y2);
                }
            }
            return res;
        }

        static class NumMatrix {
            // 定义：preSum[i][j]记录matrix中子矩阵[0,0,i-1,j-1]的元素和
            private int[][] preSum;

            public NumMatrix(int[][] matrix) {
                int m = matrix.length;
                int n = matrix[0].length;
                if (m == 0 || n == 0) {
                    return;
                }
                preSum = new int[m + 1][n + 1];
                for (int i = 1; i <= m; i++) {
                    for (int j = 1; j <= n; j++) {
                        // 计算每个矩阵[0, 0, i, j]的元素和
                        preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] + matrix[i - 1][j - 1] - preSum[i - 1][j - 1];
                    }
                }
            }

            // 计算子矩阵[x1,y1,x2,y2]的元素和
            public int sumRegion(int x1, int y1, int x2, int y2) {
                // 目标矩阵之和由四个相邻矩阵运算获得
                // preSum[x2 + 1][y2 + 1] 看作是从矩阵左上角 (0, 0) 到 (x2, y2) 这个大子矩阵的元素和。但这个大子矩阵包含了我们不需要的部分，需要减去多余的区域。
                // preSum[x1][y2 + 1]：它表示从矩阵左上角 (0, 0) 到 (x1 - 1, y2) 这个子矩阵的元素和。从 preSum[x2 + 1][y2 + 1] 中减去它，就相当于去掉了大子矩阵中 x 坐标小于 x1 的那部分区域。
                // preSum[x2 + 1][y1]：它表示从矩阵左上角 (0, 0) 到 (x2, y1 - 1) 这个子矩阵的元素和。从 preSum[x2 + 1][y2 + 1] 中减去它，就相当于去掉了大子矩阵中 y 坐标小于 y1 的那部分区域。
                // 然而，在减去 preSum[x1][y2 + 1] 和 preSum[x2 + 1][y1] 时，(0, 0) 到 (x1 - 1, y1 - 1) 这个子矩阵的和被减了两次，所以需要再加上 preSum[x1][y1] 把多减去的部分补回来。
                return preSum[x2 + 1][y2 + 1] - preSum[x1][y2 + 1] - preSum[x2 + 1][y1] + preSum[x1][y1];
            }
        }
    }

    // 724. 寻找数组的中心下标
    // 给你一个整数数组 nums ，请计算数组的 中心下标 。
    // 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
    // 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
    // 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
    // 示例 1：
    // 输入：nums = [1, 7, 3, 6, 5, 6]
    // 输出：3
    // 解释：
    // 中心下标是 3 。
    // 左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
    // 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等
    static class PivotIndex {
        public int pivotIndex(int[] nums) {
            int n = nums.length;
            int[] preSum = new int[n + 1];
            preSum[0] = 0;
            // 计算nums的前缀和
            for (int i = 1; i < preSum.length; i++) {
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
            // 根据前缀和判断左半边数组和右半边数组的元素和是否相同
            for (int i = 1; i < preSum.length; i++) {
                // 计算nums[i-1]左侧和右侧的元素和
                int leftSum = preSum[i - 1] - preSum[0]; // 0到i-1-1的元素和
                int rightSum = preSum[n] - preSum[i]; // i到n-1的元素和
                if (leftSum == rightSum) {
                    // 相对nums数组，preSum数组有一位索引偏移
                    return i - 1;
                }
            }
            return -1;
        }
    }

    // 二：前缀积
    // 除了前缀和，也可以构建前缀积数组，两个元素相除的结果是子数组的乘积，但唯一需要注意的是，要防止 0 作为除数。

    // 238. 除自身以外数组的乘积
    // 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
    // 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
    // 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
    // 示例 1:
    // 输入: nums = [1,2,3,4]
    // 输出: [24,12,8,6]
    // 基本思路
    // 这道题和前缀和数组技巧 有些类似，前缀和数组中两个元素之差是子数组元素之和，那么如果构造「前缀积」数组，两个元素相除就是子数组元素之和。
    // 所以我们构造一个 prefix 数组记录「前缀积」，再用一个 suffix 记录「后缀积」，根据前缀和后缀积就能计算除了当前元素之外其他元素的积。
    static class ProductExceptSelf {
        public int[] productExceptSelf(int[] nums) {
            int n = nums.length;
            // 从左到右的前缀积，prefix[i]是nums[0..i]的元素积
            int[] prefix = new int[n];
            prefix[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                prefix[i] = prefix[i - 1] * nums[i];
            }
            // 从右往左的前缀积，suffix[i]是nums[i..n-1]的元素积
            int[] suffix = new int[n];
            suffix[n - 1] = nums[n - 1];
            for (int i = n - 2; i >= 0; i--) {
                suffix[i] = suffix[i + 1] * nums[i];
            }
            // 结果数组
            int[] res = new int[n];
            res[0] = suffix[1];
            res[n - 1] = prefix[n - 2];
            for (int i = 1; i < n - 1; i++) {
                // 除了nums[i]子集的元素积就是nums[i]左侧和右侧所有元素之积
                res[i] = prefix[i - 1] * suffix[i + 1];
            }
            return res;
        }
    }

    // 1352. 最后 K 个数的乘积
    // 设计一个算法，该算法接受一个整数流并检索该流中最后 k 个整数的乘积。
    // 实现 ProductOfNumbers 类：
    // ProductOfNumbers() 用一个空的流初始化对象。
    // void add(int num) 将数字 num 添加到当前数字列表的最后面。
    // int getProduct(int k) 返回当前数字列表中，最后 k 个数字的乘积。你可以假设当前列表中始终 至少 包含 k 个数字。
    // 题目数据保证：任何时候，任一连续数字序列的乘积都在 32 位整数范围内，不会溢出。
    static class ProductOfNumbers {
        // 前缀积数组
        // preProduct[i] / preProduct[j] 就是 [i, j] 之间的元素积
        ArrayList<Integer> preProduct = new ArrayList<>();

        public ProductOfNumbers() {
            // 初始化放一个1，便于计算后序添加元素的乘积
            preProduct.add(1);
        }

        public void add(int num) {
            if (num == 0) {
                // 如果添加的元素是0，则前面的元素乘积都废了
                preProduct.clear();
                preProduct.add(1);
                return;
            }
            int n = preProduct.size();
            // 前缀积数组中每个元素
            preProduct.add(preProduct.get(n - 1) * num);
        }

        public int getProduct(int k) {
            int n = preProduct.size();
            if (k > n - 1) {
                // 不足k个元素，是因为最后k个元素存在0
                return 0;
            }
            // 计算最后k个元素积
            return preProduct.get(n - 1) / preProduct.get(n - k - 1);
        }
    }

    // 三：前缀和+哈希表
    // 前缀和数组帮你快速计算子数组的元素之和，但如果让你寻找某个符合条件的子数组，怎么办？
    // 比如说，让你在nums中寻找和为target的子数组，就算有前缀和数组的帮助，你也要写个嵌套for循环。
    // for (int i = 1; i < preSum.length; i++) {
    //    for (int j = 0; j < i; j++) {
    //        if (preSum[i] - preSum[j] == target) {
    //            // 找到子数组
    //        }
    //    }
    //}
    // 但我们可以借助哈希表记录每个前缀和对应的索引，这样就能快速计算目标和为target的子数组了。
    static class Demo {
        public void demo(int[] nums, int target) {
            // 前缀和到索引的映射
            HashMap<Integer, Integer> valToIndex = new HashMap<>();
            // 一般我们让preSum比num数组多一位，因为第一位要放0
            int[] preSum = new int[nums.length + 1];
            for (int j = 0; j < preSum.length; j++) {
                valToIndex.put(preSum[j], j);
            }

            for (int i = 1; i < preSum.length; i++) {
                int need = preSum[i] - target;
                if (valToIndex.containsKey(need)) {
                    // nums[valToIndex.get(need).. i-1] 就是和为 target 的子数组
                    // 注意 preSum 和 nums 有一位索引偏移，所以是 i-1
                }
            }
        }
    }

    // 525. 连续数组
    // 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
    // 示例 1：
    // 输入：nums = [0,1]
    // 输出：2
    // 说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

    // 基本思路：
    // 首先，我们做一个等价，题目让你找0和1数量相同的最长子数组，如果我们把0视作-1，就把题目转变成了：寻找和为0的最长子数组。
    // 涉及到和为xxx的子数组，就是要考察前缀和技巧和哈希表的结合使用了。
    // 求和为 0 的最长子数组，相当于让你去 preSum 数组中找 i, j，使得 preSum[i] - preSum[j] == 0，其中 i > j 且 i - j 要尽可能大。
    // 那么我们用一个哈希表 valToIndex 存储前缀和到索引的映射，给定任意 preSum[i]，
    // 我们都能通过 valToIndex 快速判断是否存在 j，使得 preSum[i] - preSum[j] == 0。
    static class FindMaxLength {
        public int findMaxLength(int[] nums) {
            int n = nums.length;
            int[] preSum = new int[n + 1];
            preSum[0] = 0;
            // 计算nums的前缀和
            for (int i = 0; i < n; i++) {
                preSum[i + 1] = preSum[i] + (nums[i] == 0 ? -1 : 1);
            }
            // 前缀和到索引的映射，方便快速查找所需的前缀和
            HashMap<Integer, Integer> valToIndex = new HashMap<>();
            int res = 0;
            for (int i = 0; i < preSum.length; i++) {
                // 如果这个前缀和还没有对应的索引，说明这个前缀和第一次出现，记录下来
                if (!valToIndex.containsKey(preSum[i])) {
                    valToIndex.put(preSum[i], i);
                } else {
                    // 这个前缀和已经出现了，则找到一个和为0的子数组
                    // i - valToIndex.get(preSum[i])：这个表达式计算的是从该前缀和首次出现的下一个位置到当前位置所构成的子数组的长度。
                    // 因为前缀和相等意味着这两个位置之间的子数组元素和为 0，也就是子数组中 0 和 1 的数量相等。
                    res = Math.max(res, i - valToIndex.get(preSum[i]));
                }
                // 因为题目想找长度最大的子数组，所以前缀和索引应尽可能小
            }
            return res;
        }

        public static void main(String[] args) {
            int[] nums = {0, 1, 1, 1, 1, 1, 0, 0, 0};
            new FindMaxLength().findMaxLength(nums);
        }
    }

    // 523. 连续的子数组和
    // 给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：
    // 一个 好的子数组 是：
    // 1. 长度 至少为 2 ，且
    // 2. 子数组元素总和为 k 的倍数。
    // 注意：
    // 子数组 是数组中 连续 的部分。
    // 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。
    // 示例 1：
    // 输入：nums = [23,2,4,6,7], k = 6
    // 输出：true
    // 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

    // 基本思路：
    // 这道题和525.连续数组非常相似，都是考察前缀和技巧和哈希表的结合使用
    // 本题让你寻找长度至少为2且和为k的倍数的子数组，翻译一下就是：
    // 寻找i,j使得(preSum[i] - preSum[j]) % k == 0且i-j>=2；
    // 另外，(preSum[i] - preSum[j]) % k == 0 其实就是 preSum[i] % k == preSum[j] % k。
    // 所以我们使用一个哈希表，记录 preSum[j] % k 的值以及对应的索引，就可以迅速判断 preSum[i] 是否符合条件了。
    static class CheckSubarraySum{
        public boolean checkSubarraySum(int[] nums, int k) {
            int n = nums.length;
            // 计算nums的前缀和
            int[] preSum = new int[n+1];
            preSum[0] = 0;
            for(int i = 1; i < preSum.length; i++){
                preSum[i] = preSum[i-1] + nums[i-1];
            }
            // 前缀和与k的余数到索引的映射，方便快速查找所需的前缀和
            HashMap<Integer, Integer> valToIndex = new HashMap<>();
            for(int i = 0; i < preSum.length; i++){
                // 在哈希表中记录余数
                int val = preSum[i] % k;
                // 如果这个余数还没有对应的索引，则记录下来
                // 记录首个位置
                if (!valToIndex.containsKey(val)){
                    valToIndex.put(val, i);
                }
                // 如果这个前缀和已经有对应的索引了，则什么都不做
                // 因为题目想找长度最大的子数组，所以前缀和索引应尽可能小
            }
            for(int i = 1; i < preSum.length; i++){
                // 计算need，使得(preSum[i] - need) % k == 0;
                int need = preSum[i] % k;
                if (valToIndex.containsKey(need)){
                    // 此代码旨在判定数组 nums 中是否存在一个长度至少为 2 的连续子数组，其元素总和是 k 的倍数。
                    if (i - valToIndex.get(need) >= 2){
                        // 这个子数组的长度至少为2
                        return true;
                    }
                }
            }
            return false;
        }
    }

    // 560. 和为 K 的子数组
    // 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
    // 子数组是数组中元素的连续非空序列。
    // 示例 1：
    // 输入：nums = [1,1,1], k = 2
    // 输出：2
    static class SubarraySum{
        public int subarraySum(int[] nums, int k) {
            int n = nums.length;
            // 前缀和数组
            int[] preSum = new int[n+1];
            preSum[0] = 0;
            // 前缀和到该前缀和出现次数的映射，方便快速查找所需的前缀和
            HashMap<Integer, Integer> count = new HashMap<>();
            count.put(0, 1);
            // 记录和为k的子数组个数
            int res = 0;
            // 计算nums的前缀和
            for(int i = 1; i < preSum.length; i++){
                preSum[i] = preSum[i-1] + nums[i-1];
                // 如果之前存在值为need的前缀和
                // 说明存在以nums[i-1]结尾的子数组的和为k
                int need = preSum[i] - k;
                if (count.containsKey(need)){
                    res += count.get(need);
                }
                // 将当前前缀和存入哈希表
                if (!count.containsKey(preSum[i])){
                    count.put(preSum[i], 1);
                }else{
                    count.put(preSum[i], count.get(preSum[i]) + 1);
                }
            }
            return res;
        }

        public static void main(String[] args) {
            int[] nums = new int[]{1,2,3};
            new SubarraySum().subarraySum(nums, 3);
        }
    }
}
